﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.IO;
using System.Reflection;
using System.Diagnostics;
using System.Runtime.InteropServices;
using Microsoft.Win32;


namespace PidProject
{
    public class SimpleOcr
    {
        public static string Revision = "$Revision: 1.6 $";

        // threshold for converting color bitmap to black-white
        public int BW_threshold = 230;

        // parameters of a single LED digit ("prototype" in Tesseact terminology)
        public int ProtoW = 25; // width
        public int ProtoH = 50; // height
        public int ProtoD = 6;  // delta at the top (for the char tilt)
        public int ProtoT = 6;  // thickness of the char

        public int ProtoM_1 = -19; // move the prototype for a given digit to have a better fit
        public int ProtoM_4 = -5;

        public struct Pair
        {
            public int x;
            public int y;

            public Pair(int _x, int _y) { x = _x; y = _y; }
        }

        public struct Segment
        {
            public static int protoD = 0;
            public static int protoH = 0;
            public static double scale = 1;

            public int x1;
            public int y1;
            public int x2;
            public int y2;

            private static double xshift(double h) // shift the x-coordinate at the height h (due to char "tilt")
            {
                return protoD * h / protoH;
            }

            private static int round(double d) { return (int)(0.5 + d); }

            public Segment(int _x1, int _y1, int _x2, int _y2)
            {
                x1 = round((_x1 + xshift(_y1)) * scale);
                y1 = round(_y1 * scale);
                x2 = round((_x2 + xshift(_y2)) * scale);
                y2 = round(_y2 * scale);
            }

            public Segment ShiftX(int delta)  // shift the segment
            {
                x1 = round(delta * scale + x1);
                x2 = round(delta * scale + x2);

                Segment s = new Segment();
                s.x1 = x1;
                s.x2 = x2;
                s.y1 = y1;
                s.y2 = y2;

                return s;
            }

            public double getLength()
            {
                return Math.Sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
            }
        }
        public class Candidate  // used for "proper OCR, simiar to Tesseract algorithm
        {
            public List<Segment> lst = new List<Segment>();
            public void ShiftX(int delta)
            {
                for (int i = 0; i < lst.Count; i++)
                    lst[i] = lst[i].ShiftX(delta);
            }
        }
        public class SimpleCandidate
        {
            public Dictionary<int, bool> d = new Dictionary<int, bool>();
            public void add(int[] lst)
            {
                foreach (int i in lst)
                    d.Add(i, false);
            }
            public void add(int i)
            {
                d.Add(i, false);
            }
            public bool is_equal(SimpleCandidate s)
            {
                foreach (int k in d.Keys)
                {
                    if (!s.d.ContainsKey(k))
                        return false;
                }
                foreach (int k in s.d.Keys)
                {
                    if (!d.ContainsKey(k))
                        return false;
                }

                return true;
            }
        }

        public enum BlobType { Blob, Vertical, Horizontal }
        public struct BlobInfo
        {
            public int xmin;
            public int xmax;
            public int ymin;
            public int ymax;

            public BlobInfo(bool reset)
            {
                xmin = 0;
                xmax = 0;
                ymin = 0;
                ymax = 0;
                if (reset)
                {
                    xmin = int.MaxValue;
                    xmax = int.MinValue;
                    ymin = int.MaxValue;
                    ymax = int.MinValue;
                }
            }
            public void Update(int x, int y)
            {
                xmin = Math.Min(xmin, x);
                xmax = Math.Max(xmax, x);
                ymin = Math.Min(ymin, y);
                ymax = Math.Max(ymax, y);
            }
            public int GetCenterX()
            {
                return (xmin + xmax) / 2;
            }
            public int GetCenterY()
            {
                return (ymin + ymax) / 2;
            }
            public int GetSizeX()
            {
                return xmax - xmin;
            }
            public int GetSizeY()
            {
                return ymax - ymin;
            }
            public BlobType GetBlobType()
            {
                double ratio = (double)(xmax - xmin) / (double)(ymax - ymin);
                if (ratio < 0.5) return BlobType.Vertical;
                else if (ratio > 1.9) return BlobType.Horizontal;
                else return BlobType.Blob;
            }
        }

        List<Candidate> CandidateList = new List<Candidate>();
        List<SimpleCandidate> SimpleCandidateList = new List<SimpleCandidate>();
        public void FillCandidateList(int bmpH)
        {
            CandidateList.Clear();
            SimpleCandidateList.Clear();

            Segment.protoD = ProtoD;
            Segment.protoH = ProtoH;
            Segment.scale = (double)(bmpH - 1) / (double)(ProtoH + 1);

            // some key points (in addition to 0, H and W)
            int h1 = ProtoT;
            int h2 = ProtoH / 2 - ProtoT / 2;
            int h3 = ProtoH / 2 + ProtoT / 2;
            int h4 = ProtoH - ProtoT;
            int w1 = ProtoT;
            int w2 = ProtoW - ProtoT;

            // LED digit contains 7 segments, we number them clockwise, starting from the bottom left as 1..6. The middle one is 7

            Segment s1 = new Segment(0, h1, 0, h2);
            Segment s1a = new Segment(w1, h1, w1, h2);

            Segment s2 = new Segment(0, h3, 0, h4);
            Segment s2a = new Segment(w1, h3, w1, h4);

            Segment s3 = new Segment(w1, ProtoH, w2, ProtoH);
            Segment s3a = new Segment(w1, h4, w2, h4);

            Segment s4 = new Segment(ProtoW, h3, ProtoW, h4);
            Segment s4a = new Segment(w2, h3, w2, h4);

            Segment s5 = new Segment(ProtoW, h1, ProtoW, h2);
            Segment s5a = new Segment(w2, h1, w2, h2);

            Segment s6 = new Segment(w1, 0, w2, 0);
            Segment s6a = new Segment(w1, h1, w2, h1);

            Segment s7 = new Segment(w1, h3, w2, h3);
            Segment s7a = new Segment(w1, h2, w2, h2);

            Candidate cand = new Candidate(); CandidateList.Add(cand);  // digit "0"
            cand.lst.Add(s1); cand.lst.Add(s2); cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s5); cand.lst.Add(s6);
            cand.lst.Add(s1a); cand.lst.Add(s2a); cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s5a); cand.lst.Add(s6a);

            cand = new Candidate(); CandidateList.Add(cand);  // "1"
            cand.lst.Add(s4); cand.lst.Add(s5);
            cand.lst.Add(s4a); cand.lst.Add(s5a);

            cand = new Candidate(); CandidateList.Add(cand);  // "2"
            cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s7); cand.lst.Add(s1); cand.lst.Add(s6);
            cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s7a); cand.lst.Add(s1a); cand.lst.Add(s6a);

            cand = new Candidate(); CandidateList.Add(cand);  // "3"
            cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s7); cand.lst.Add(s5); cand.lst.Add(s6);
            cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s7a); cand.lst.Add(s5a); cand.lst.Add(s6a);

            cand = new Candidate(); CandidateList.Add(cand);  // "4"
            cand.lst.Add(s2); cand.lst.Add(s4); cand.lst.Add(s7); cand.lst.Add(s5);
            cand.lst.Add(s2a); cand.lst.Add(s4a); cand.lst.Add(s7a); cand.lst.Add(s5a);

            cand = new Candidate(); CandidateList.Add(cand);  // "5"
            cand.lst.Add(s3); cand.lst.Add(s2); cand.lst.Add(s7); cand.lst.Add(s5); cand.lst.Add(s6);
            cand.lst.Add(s3a); cand.lst.Add(s2a); cand.lst.Add(s7a); cand.lst.Add(s5a); cand.lst.Add(s6a);

            cand = new Candidate(); CandidateList.Add(cand);  // "6"
            cand.lst.Add(s3); cand.lst.Add(s2); cand.lst.Add(s7); cand.lst.Add(s5); cand.lst.Add(s6); cand.lst.Add(s1);
            cand.lst.Add(s3a); cand.lst.Add(s2a); cand.lst.Add(s7a); cand.lst.Add(s5a); cand.lst.Add(s6a); cand.lst.Add(s1a);

            cand = new Candidate(); CandidateList.Add(cand);  // "7"
            cand.lst.Add(s2); cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s5);
            cand.lst.Add(s2a); cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s5a);

            cand = new Candidate(); CandidateList.Add(cand);  // "8"
            cand.lst.Add(s1); cand.lst.Add(s2); cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s5); cand.lst.Add(s6); cand.lst.Add(s7);
            cand.lst.Add(s1a); cand.lst.Add(s2a); cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s5a); cand.lst.Add(s6a); cand.lst.Add(s7a);

            cand = new Candidate(); CandidateList.Add(cand);  // "9"
            cand.lst.Add(s2); cand.lst.Add(s3); cand.lst.Add(s4); cand.lst.Add(s5); cand.lst.Add(s6); cand.lst.Add(s7);
            cand.lst.Add(s2a); cand.lst.Add(s3a); cand.lst.Add(s4a); cand.lst.Add(s5a); cand.lst.Add(s6a); cand.lst.Add(s7a);

            // apply shifts
            CandidateList[1].ShiftX(ProtoM_1);
            CandidateList[4].ShiftX(ProtoM_4);


            // Now fill the simple candidate list
            SimpleCandidate s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "0"
            s_cand.add(new int[] { 1, 2, 3, 4, 5, 6 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "1"
            s_cand.add(new int[] { 4, 5 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "2"
            s_cand.add(new int[] { 3, 4, 7, 1, 6 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "3"
            s_cand.add(new int[] { 3, 4, 7, 5, 6 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "4"
            s_cand.add(new int[] { 2, 4, 7, 5 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "5"
            s_cand.add(new int[] { 3, 2, 7, 5, 6 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "6"
            s_cand.add(new int[] { 3, 2, 7, 5, 6, 1 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "7"
            s_cand.add(new int[] { 2, 3, 4, 5 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "8"
            s_cand.add(new int[] { 1, 2, 3, 4, 5, 6, 7 });

            s_cand = new SimpleCandidate(); SimpleCandidateList.Add(s_cand);  // "9"
            s_cand.add(new int[] { 2, 3, 4, 5, 6, 7 });
        }

        // ======== Bitmap procs ==================

        public void ToBlackWhite(Bitmap bmp)
        {
            BitmapData bmpData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadWrite, bmp.PixelFormat);

            int bpp = bmp.PixelFormat == PixelFormat.Format24bppRgb ? 3 : 4; // support 3 and 4 bpp only

            byte[] rgbValues = new byte[Math.Abs(bmpData.Stride) * bmp.Height];

            Marshal.Copy(bmpData.Scan0, rgbValues, 0, rgbValues.Length); // copy data from bmp

            // convert into BW
            for (int counter = 0; counter < rgbValues.Length; counter += bpp)
            {
                if (rgbValues[counter] + rgbValues[counter + 1] + rgbValues[counter + 2] > BW_threshold * 3)
                {
                    rgbValues[counter] = 255;
                    rgbValues[counter + 1] = 255;
                    rgbValues[counter + 2] = 255;
                }
                else
                {
                    rgbValues[counter] = 0;
                    rgbValues[counter + 1] = 0;
                    rgbValues[counter + 2] = 0;

                }
            }

            Marshal.Copy(rgbValues, 0, bmpData.Scan0, rgbValues.Length); // copy data from bmp
            bmp.UnlockBits(bmpData);
        }
        public bool ChopBitmapIntoWords(Bitmap bmp, ref List<Bitmap> words)
        {
            BitmapData bmpData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadWrite, bmp.PixelFormat);

            int bpp = bmp.PixelFormat == PixelFormat.Format24bppRgb ? 3 : 4; // support 3 and 4 bpp only

            int row_len = Math.Abs(bmpData.Stride);
            byte[] rgbValues = new byte[row_len * bmp.Height];

            Marshal.Copy(bmpData.Scan0, rgbValues, 0, rgbValues.Length); // copy data from bmp


            // First crop top and bottom, starting from the center
            int top = bmp.Height / 2;
            for (int j = bmp.Height / 2; j >= 0; j--)
            {
                bool white_found = false;
                for (int i = 0; i < bmp.Width; i++)
                {
                    if (rgbValues[j * row_len + i * bpp] == 255)
                    {
                        white_found = true;
                        break;
                    }
                }

                if (!white_found && j == bmp.Height / 2)
                    return false;  // center line do not have data

                if (!white_found)
                {
                    top = j + 1;
                    break;
                }
            }

            int bot = bmp.Height / 2;
            for (int j = bmp.Height / 2; j < bmp.Height; j++)
            {
                bool white_found = false;
                for (int i = 0; i < bmp.Width; i++)
                {
                    if (rgbValues[j * row_len + i * bpp] == 255)
                    {
                        white_found = true;
                        break;
                    }
                }

                if (!white_found)
                {
                    bot = j - 1;
                    break;
                }
            }

            List<Rectangle> copy_list = new List<Rectangle>();
            int start = -1;
            for (int i = 0; i < bmp.Width; i++)
            {
                bool white_found = false;
                for (int j = top; j <= bot; j++)
                {
                    if (rgbValues[j * row_len + i * bpp] == 255)
                    {
                        white_found = true;
                        break;
                    }
                }

                if (start == -1 && white_found)
                    start = i;
                else if (start != -1 && !white_found)
                {
                    copy_list.Add(new Rectangle(start, top, i - start, bot - top + 1));
                    start = -1;
                }
            }

            // unlock bmp and copy the regions
            bmp.UnlockBits(bmpData);

            words.Clear();
            foreach (Rectangle r in copy_list)
                words.Add(CopyRegionIntoImage(bmp, r));

            return true;

        }
        public Bitmap CopyRegionIntoImage(Bitmap srcBitmap, Rectangle srcRegion)
        {
            Rectangle destRegion = new Rectangle(0, 0, srcRegion.Width, srcRegion.Height);
            Bitmap destBitmap = new Bitmap(srcRegion.Width, srcRegion.Height);
            using (Graphics grD = Graphics.FromImage(destBitmap))
                grD.DrawImage(srcBitmap, destRegion, srcRegion, GraphicsUnit.Pixel);

            return destBitmap;
        }

        // ======== Simple (blob-based) OCR ==================

        public void DetectRegions(Bitmap bmp, int decimal_dot_location, ref List<BlobInfo> blobs)
        {
            blobs.Clear();

            BitmapData bmpData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadWrite, bmp.PixelFormat);

            int bpp = bmp.PixelFormat == PixelFormat.Format24bppRgb ? 3 : 4; // support 3 and 4 bpp only

            int row_len = Math.Abs(bmpData.Stride);
            byte[] rgbValues = new byte[row_len * bmp.Height];

            Marshal.Copy(bmpData.Scan0, rgbValues, 0, rgbValues.Length); // copy data from bmp

            // remove the decimal dot bits
            if (decimal_dot_location < bmp.Height && decimal_dot_location < bmp.Width)
                for (int i = bmp.Width - decimal_dot_location; i < bmp.Width; i++)
                    for (int j = bmp.Height - decimal_dot_location; j < bmp.Height; j++)
                        rgbValues[j * row_len + i * bpp] = 0;

            // detect whites and flood-fill the region with blob-id
            for (int i = 0; i < bmp.Width; i++)
            {
                for (int j = 0; j < bmp.Height; j++)
                {
                    if (rgbValues[j * row_len + i * bpp] == 255)
                    {
                        BlobInfo blob = new BlobInfo(true);
                        FloodFill(rgbValues, bmp.Width, bmp.Height, row_len, bpp, i, j, (byte)(blobs.Count + 1), ref blob);

                        if (blob.GetSizeX() > 1 && blob.GetSizeY() > 1) // skip one-pixel blobs
                            blobs.Add(blob);
                    }
                }
            }


            bmp.UnlockBits(bmpData);
        }

        public void FloodFill(byte[] rgbValues, int W, int H, int row_len, int bpp,  // bmp data
                                     int x, int y, byte blob_id, ref BlobInfo blob)
        {
            List<Pair> lst = new List<Pair>();
            lst.Add(new Pair(x, y));
            rgbValues[y * row_len + x * bpp] = blob_id;

            while (lst.Count > 0)
            {
                Pair p = lst[0];
                blob.Update(p.x, p.y);
                lst.RemoveAt(0);

                int index = p.y * row_len + (p.x - 1) * bpp;
                if (p.x != 0 && rgbValues[index] == 255)
                {
                    lst.Add(new Pair(p.x - 1, p.y));
                    rgbValues[index] = blob_id;
                }

                index = (p.y - 1) * row_len + p.x * bpp;
                if (p.y != 0 && rgbValues[index] == 255)
                {
                    lst.Add(new Pair(p.x, p.y - 1));
                    rgbValues[index] = blob_id;
                }

                index = (p.y + 1) * row_len + p.x * bpp;
                if (p.y != (H - 1) && rgbValues[index] == 255)
                {
                    lst.Add(new Pair(p.x, p.y + 1));
                    rgbValues[index] = blob_id;
                }

                index = p.y * row_len + (p.x + 1) * bpp;
                if (p.x != (W - 1) && rgbValues[index] == 255)
                {
                    lst.Add(new Pair(p.x + 1, p.y));
                    rgbValues[index] = blob_id;
                }
            }

            // flip the blob to have axix Y up
            int ymin = blob.ymin;
            int ymax = blob.ymax;
            blob.ymax = H - 1 - ymin;
            blob.ymin = H - 1 - ymax;
        }

        // ======== Simple (ray-based) OCR ==================

        public bool DetectRays(Bitmap bmp, int decimal_dot_location, ref List<int> ray_width)
        {
            ray_width.Clear();

            BitmapData bmpData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadWrite, bmp.PixelFormat);

            int bpp = bmp.PixelFormat == PixelFormat.Format24bppRgb ? 3 : 4; // support 3 and 4 bpp only

            int row_len = Math.Abs(bmpData.Stride);
            byte[] rgbValues = new byte[row_len * bmp.Height];

            Marshal.Copy(bmpData.Scan0, rgbValues, 0, rgbValues.Length); // copy data from bmp

            // remove the decimal dot bits
            if (decimal_dot_location < bmp.Height && decimal_dot_location < bmp.Width)
                for (int i = bmp.Width - decimal_dot_location; i < bmp.Width; i++)
                    for (int j = bmp.Height - decimal_dot_location; j < bmp.Height; j++)
                        rgbValues[j * row_len + i * bpp] = 0;

            // Trace the rays from the bottom black area
            int x0 = bmp.Width/2;
            int xd = ProtoD / 2;
            int y0_B = bmp.Height / 3;    // Note the bitmap is top down, so we flip T and B
            int y0_T = bmp.Height * 2 / 3;

            if (rgbValues[y0_B * row_len + x0 * bpp] != 0 || rgbValues[y0_T * row_len + x0 * bpp] != 0)  // the starting point(s) are not black
            {
                bmp.UnlockBits(bmpData);
                return false;
            }

            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 - xd, y0_T, RayDirection.Left));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 + xd, y0_B, RayDirection.Left));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 + xd, y0_B, RayDirection.Bot));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 + xd, y0_B, RayDirection.Right));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 - xd, y0_T, RayDirection.Right));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 - xd, y0_T, RayDirection.Top));
            ray_width.Add(TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 - xd, y0_T, RayDirection.Bot) +
                          TraceRays(rgbValues, bmp.Width, bmp.Height, row_len, bpp, x0 + xd, y0_B, RayDirection.Top));

            bmp.UnlockBits(bmpData);
            return true;
        }

        // trace a black "ray" from a point x, y into a given direction. If the ray reaches the boundary or H/2, 
        // return true
        public enum RayDirection { Top, Bot, Left, Right }
        public int TraceRays(byte[] rgbValues, int W, int H, int row_len, int bpp,  // bmp data
                             int x0, int y0, RayDirection dir)
        {
            int num_rays = 0;

            int minH = y0 < H / 2 ? 0 : H / 2;
            int maxH = y0 < H / 2 ? H / 2 : H;

            if (dir == RayDirection.Left)
            {
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, -1, 0, 0, 1);
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, -1, 0, 0, -1);
            }
            else if (dir == RayDirection.Right)
            {
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 1, 0, 0, 1);
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 1, 0, 0, -1);
            }
            else if (dir == RayDirection.Top)
            {
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 0, 1, 1, 0);
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 0, 1, -1, 0);
            }
            else if (dir == RayDirection.Bot)
            {
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 0, -1, 1, 0);
                num_rays += TraceRayUtil(rgbValues, W, minH, maxH, row_len, bpp, x0, y0, 0, -1, -1, 0);
            }

            return num_rays;
        }

        public int TraceRayUtil(byte[] rgbValues, int W, int minH, int maxH, int row_len, int bpp,  // bmp data
                                int x0, int y0, int dx, int dy, int dx0, int dy0)
        {
            int num_rays = 0;

            while (true)
            {
                if (x0 < 0 || x0 >= W || y0 < minH || y0 >= maxH)
                    break;

                bool ray_traced = true;

                int i = x0;
                int j = y0;
                while (true)
                {
                    if (i < 0 || i >= W || j < minH || j >= maxH)
                        break;

                    if(rgbValues[j * row_len + i * bpp] != 0)
                    {
                        ray_traced = false;
                        break;
                    }

                    i += dx;
                    j += dy;
                }

                if (!ray_traced)
                    break;

                num_rays++;
                x0 += dx0;
                y0 += dy0;
            }

            return num_rays;
        }


        // return a digit 0..9, or -1 if cannot match any candidate
        public int MatchSimpleCandidate(List<BlobInfo> blobs, int W, int H)
        {
            // create a candidate given a set a blobs
            SimpleCandidate cnd = new SimpleCandidate();
            foreach (BlobInfo b in blobs)
            {
                if (W < H * 0.4) // special case of "narrow" 1
                {
                    if (b.GetBlobType() == BlobType.Horizontal)  // no horizontal in 1
                        return -1;

                    if (b.GetCenterY() < H / 2)
                        cnd.add(5);
                    else if (b.GetCenterY() > H / 2)
                        cnd.add(4);
                }
                else
                {
                    if (b.GetBlobType() == BlobType.Blob)  // all data must be H or V, Blobs means we cannot recognize it
                        return -1;

                    if (b.GetBlobType() == BlobType.Horizontal)
                    {
                        if (b.GetCenterY() < H / 3)
                            cnd.add(6);
                        else if (b.GetCenterY() > 2 * H / 3)
                            cnd.add(3);
                        else
                            cnd.add(7);
                    }
                    else
                    {
                        if (b.GetCenterX() < W / 2)
                        {
                            if (b.GetCenterY() < H / 2)
                                cnd.add(1);
                            else if (b.GetCenterY() > H / 2)
                                cnd.add(2);
                        }
                        else
                        {
                            if (b.GetCenterY() < H / 2)
                                cnd.add(5);
                            else if (b.GetCenterY() > H / 2)
                                cnd.add(4);
                        }
                    }
                }
            }

            for (int i = 0; i < SimpleCandidateList.Count; i++)
            {
                if (cnd.is_equal(SimpleCandidateList[i]))
                    return i;
            }

            return -1;
        }

        // matching routine for OCR2
        public int MatchSimpleCandidate2(List<int> ray_width)
        {
            // create a candidate given a set a blobs
            SimpleCandidate cnd = new SimpleCandidate();

            for(int i = 0; i < ray_width.Count; i++)
            {
                if (ray_width[i] > 4)  // make sure that we traced > 4 rays
                    continue;

                cnd.add(i+1);
            }

            for (int i = 0; i < SimpleCandidateList.Count; i++)
            {
                if (cnd.is_equal(SimpleCandidateList[i]))
                    return i;
            }

            return -1;
        }


        // ======== Tesseract-style OCR (feature/proto distance -based) ==================

        // the function to calculate the distance between point and a segment
        private int Pair2SegmentSquareDistance(Pair p, Segment s)
        {
            // segment coord moved into segment origin
            int x1 = s.x2 - s.x1;
            int y1 = s.y2 - s.y1;

            // point coord moved into segment origin
            int x2 = p.x - s.x1;
            int y2 = p.y - s.y1;

            // square length and the scalar product
            int L1_2 = x1 * x1 + y1 * y1;
            int L2_2 = x2 * x2 + y2 * y2;
            int L_12 = x1 * x2 + y1 * y2;

            if (L_12 < 0)  // projection does not hit the segment, the vactors are looking different ways
                return int.MaxValue;
            if (L_12 > L1_2)  // projection does not hit the segment - too long to land on the segment
                return int.MaxValue;

            return L2_2 - L_12 * L_12 / L1_2;
        }

        public List<double> CalcCandidateEvidence(List<Pair> o)
        {
            List<double> evd = new List<double>();
            foreach (Candidate c in CandidateList)
                evd.Add(0);

            if (o.Count == 0)
                return evd;

            // feature evidence - select the min distance to a segment(proto) for each feature
            List<double> evd_feature = new List<double>();
            foreach (Candidate c in CandidateList)
                evd_feature.Add(0);

            foreach (Pair p in o)
            {
                for (int cand_i = 0; cand_i < CandidateList.Count; cand_i++)
                {
                    int min_d2 = int.MaxValue;
                    foreach (Segment s in CandidateList[cand_i].lst)
                        min_d2 = Math.Min(min_d2, Pair2SegmentSquareDistance(p, s));

                    evd_feature[cand_i] += 1.0 / (1.0 + min_d2);
                }
            }


            // Proto evidence - select top "lenght" features for a given proto
            List<double> evd_proto = new List<double>();
            List<double> proto_length = new List<double>();
            foreach (Candidate c in CandidateList)
            {
                evd_proto.Add(0);
                proto_length.Add(0);
            }

            const int proto_weight = 5;

            for (int cand_i = 0; cand_i < CandidateList.Count; cand_i++)
            {
                foreach (Segment s in CandidateList[cand_i].lst)
                {
                    List<int> d2 = new List<int>();
                    foreach (Pair p in o)
                        d2.Add(Pair2SegmentSquareDistance(p, s));

                    d2.Sort();

                    int len = (int)s.getLength();
                    proto_length[cand_i] += proto_weight * len;

                    double evidence_for_s = 0;
                    foreach (int d in d2)
                    {
                        if (len <= 0)
                            break;

                        evidence_for_s += 1.0 / (1.0 + d);
                        len--;
                    }
                    evd_proto[cand_i] += proto_weight * evidence_for_s;
                }
            }

            // final evidence value
            for (int cand_i = 0; cand_i < CandidateList.Count; cand_i++)
                evd[cand_i] = (evd_feature[cand_i] + evd_proto[cand_i]) / (o.Count + proto_length[cand_i]);

            return evd;
        }

        public List<Pair> MakeOutline(Bitmap bmp, int decimal_dot_location, bool cut_into_separate_outlines, ref List<List<Pair>> o_sets)
        {
            List<Pair> o = new List<Pair>();
            List<Pair> o_to_return = new List<Pair>();

            int W = bmp.Width;
            int H = bmp.Height;

            BitmapData bmpData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadWrite, bmp.PixelFormat);

            int bpp = bmp.PixelFormat == PixelFormat.Format24bppRgb ? 3 : 4; // support 3 and 4 bpp only

            int row_len = Math.Abs(bmpData.Stride);
            byte[] rgbValues = new byte[row_len * bmp.Height];

            Marshal.Copy(bmpData.Scan0, rgbValues, 0, rgbValues.Length); // copy data from bmp

            // remove the decimal dot bits
            if (decimal_dot_location < bmp.Height && decimal_dot_location < bmp.Width)
                for (int i = bmp.Width - decimal_dot_location; i < bmp.Width; i++)
                    for (int j = bmp.Height - decimal_dot_location; j < bmp.Height; j++)
                        rgbValues[j * row_len + i * bpp] = 0;

            for (int i = 0; i < W; i++)
            {
                for (int j = 0; j < H; j++)
                {
                    if (rgbValues[j * row_len + i * bpp] != 255)
                        continue;

                    int num_white = 0;

                    int index = j * row_len + (i - 1) * bpp;
                    if (i != 0 && rgbValues[index] == 255) num_white++;

                    index = (j - 1) * row_len + i * bpp;
                    if (j != 0 && rgbValues[index] == 255) num_white++;

                    index = (j + 1) * row_len + i * bpp;
                    if (j != (H - 1) && rgbValues[index] == 255) num_white++;

                    index = j * row_len + (i + 1) * bpp;
                    if (i != (W - 1) && rgbValues[index] == 255) num_white++;

                    if (num_white != 0 && num_white != 4)
                    {
                        o_to_return.Add(new Pair(i, H - 1 - j));

                        if(cut_into_separate_outlines)
                            o.Add(new Pair(i, H - 1 - j));
                    }
                }
            }

            // copy into the output
            while (cut_into_separate_outlines)
            {
                if (o.Count == 0)
                    break;

                List<Pair> new_o = new List<Pair>();
                o_sets.Add(new_o);

                Pair ref_p = o[0];
                new_o.Add(ref_p);
                o.RemoveAt(0);

                while (true)
                {
                    Pair p = new Pair();
                    if (!getNext(ref o, ref_p.x, ref_p.y, ref p))
                        break;

                    new_o.Add(p);
                    ref_p = p;
                }
            }

            bmp.UnlockBits(bmpData);
            return o_to_return;
        }

        private bool getNext(ref List<Pair> o, int i, int j, ref Pair p_out)
        {
            // first try to find the next pair with the same x and y
            for (int k = 0; k < o.Count; k++)
            {
                Pair p = o[k];

                if ((Math.Abs(p.x - i) == 1 && p.y == j) || (Math.Abs(p.y - j) == 1 && p.x == i))
                {
                    p_out = p;
                    o.RemoveAt(k);
                    return true;
                }
            }

            // now try the "diagonals"
            for (int k = 0; k < o.Count; k++)
            {
                Pair p = o[k];

                if (Math.Abs(p.x - i) <= 1 && Math.Abs(p.y - j) <= 1)
                {
                    p_out = p;
                    o.RemoveAt(k);
                    return true;
                }
            }

            return false;
        }
    }
}